# # -*- coding:utf-8 -*-
# class Solution:
#     def GetNumberOfK(self, data, k):
#         # write code here
#         # 复杂度为n的算法
#         res = 0
#         for i in range(len(data)):
#             if data[i] == k:
#                 res += 1
#         return res

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        k_left = k - 0.5
        k_right = k + 0.5

        print(self.getloc(data, k_right))
        print(self.getloc(data, k_left))
        return self.getloc(data, k_right) - self.getloc(data, k_left)

    def getloc(self, data, k):
        r = len(data)-1
        l = 0
        # print('r is %d' % r)
        # print('k is %f' % k)
        while l <= r:
            mid = (r-l) // 2 + l
            # print(data[mid])
            if data[mid] > k:
                r = mid - 1
            else:
                l = mid + 1
            # print('l is %d' % l)
            # print('r is %d' % r)

        return l

test = Solution()
print(test.GetNumberOfK([3,3,3,3,4,5], 3))